package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func constructFromPrePost(pre []int, post []int) *TreeNode {
	if len(pre) == 0 || len(post) == 0 {
		return nil
	}
	root := &TreeNode{Val: pre[0]}
	if len(pre) == 1 {
		return root
	}
	pivot := 0
	for i, v := range post {
		if v == pre[1] {
			pivot = i + 1
		}
	}
	root.Left = constructFromPrePost(pre[1:pivot+1], post[0:pivot])
	root.Right = constructFromPrePost(pre[pivot+1:], post[pivot:len(post)-1])
	return root
}

func main() {
	pre := []int{1, 2, 4, 5, 3, 6, 7}
	post := []int{4, 5, 2, 6, 7, 3, 1}
	constructFromPrePost(pre, post)
}
